/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
// 这样递归超时了，所以需要记忆状态（不会）
var wordBreak = function(s, wordDict) {
    let slen = s.length
    const dfs = (start, dict) => {
        let dlen = dict.length
        if(start + dlen > slen) return false
        if(start.substring(start, start + dlen) !== dict) return false
        let flag = false
        for(let i = 0; i < wordDict.length; i++) {
            let tempFlag = dfs(start + dlen,  wordDict[i])
            flag = flag || tempFlag
        }
        return flag
    }
    for(let i = 0; i < wordDict.length; i++) {
        if(dfs(0, wordDict[i])) return true
    }
    return false
};
// 动态规划
var wordBreak = function(s, wordDict) {
    const wordSet = new Set(wordDict)
    const len = s.length
    const dp = new Array(len + 1).fill(false)
    dp[0] = true
    for(let i = 1; i <= len; i++) {
        for(let j = i - 1; j >= 0; j--) {
            const suffix = s.slice(j, i)
            if(wordSet.has(suffix) && dp[j]) {
                dp[i] = true
                break
            }
        }
    }
    return dp[len]
}